package leetcode.recursive;

/**
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
 */
public class LeetCode52_NQueen {

    public int totalNQueens(int n) {
        return f(0, new int[n], n);
    }

    public int f(int i, int[] position, int n) {
        if (i == n) {
            return 1;
        }
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if (check(position, i, j)) {
                position[i] = j;
                sum += f(i + 1, position, n);
            }
        }
        return sum;
    }

    public boolean check(int[] position, int i, int j) {
        for (int k = 0; k < i; k++) {
            if (position[i] == j || (Math.abs(k - i) == Math.abs(position[k] - j))) {
                return false;
            }
        }
        return true;
    }

}
